class Solution {
    unordered_map<int, int> map; // inorder的元素和下标映射
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int prei = 0, sz = inorder.size();
        for(int i = 0; i < sz; ++i)
        {
            map[inorder[i]] = i;
        }
		return _buildTree(preorder, inorder, prei, 0, inorder.size() - 1);
    }

    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int left, int right)
	{
        if(left > right)
            return nullptr;

        TreeNode* root = new TreeNode(preorder[prei++]);
        /*int ini = left;
        while(inorder[ini] != root->val)
        {
            ++ini;
        }*/
        int ini = map[root->val];
        root->left = _buildTree(preorder, inorder, prei, left, ini - 1);
        root->right = _buildTree(preorder, inorder, prei, ini + 1, right);
        return root;
	}
};